package com.ronz.binarytree;

/**
 * @Description 演示二叉树的遍历：前序遍历、中序遍历、后序遍历
 * @Author Ronz
 * @Date 2021/1/17 16:38
 * @Version 1.0
 */
public class No1_BinaryTreeTraverse {
    public static void main(String[] args) {
        HeroNode node_1 = new HeroNode(1, "宋江");
        HeroNode node_2 = new HeroNode(2, "卢俊义");
        HeroNode node_3 = new HeroNode(3, "吴用");
        HeroNode node_4 = new HeroNode(4, "公孙胜");
        HeroNode node_5 = new HeroNode(5, "关胜");

        BinaryTree binaryTree = new BinaryTree(node_1);
        node_1.addLeftNode(node_2);
        node_1.addRightNode(node_3);
        node_3.addLeftNode(node_4);
        node_3.addRightNode(node_5);

//        System.out.println("前序遍历");
//        binaryTree.preOrder();  // 前序遍历
//        System.out.println("中序遍历");
//        binaryTree.midOrder();  // 中序遍历
//        System.out.println("后序遍历");
//        binaryTree.postOrder(); // 后序遍历

//        binaryTree.preOrderSearch(4); // 前序查找
//        binaryTree.midOrderSearch(6); // 中序查找
//        binaryTree.postOrderSearch(6);    // 后序查找


        binaryTree.deleteNode(3);   // 删除编号为 3 的节点
        binaryTree.preOrder();
    }
}

class BinaryTree{
    private HeroNode root;  // 根节点

    public BinaryTree(HeroNode node){
        this.root = node;
    }

    // 前序遍历
    public void preOrder(){
        if (root != null){
            root.preOrder();
        }else{
            System.out.println("二叉树为空！");
        }
    }
    // 中序遍历
    public void midOrder(){
        if (root != null){
            root.midOrder();
        }else{
            System.out.println("二叉树为空！");
        }
    }
    // 后序遍历
    public void postOrder(){
        if (root != null){
            root.postOrder();
        }else{
            System.out.println("二叉树为空！");
        }
    }
    // 前序查找
    public void preOrderSearch(int no){
        if (root != null){
            HeroNode res = root.preOrderSearch(no);
            if (res != null){
                System.out.println(res);
            }else{
                System.out.println("未找到指定节点！");
            }
        }else{
            System.out.println("二叉树为空！");
        }
    }
    // 中序查找
    public void midOrderSearch(int no){
        if (root != null){
            HeroNode res = root.midOrderSearch(no);
            if (res != null){
                System.out.println(res);
            }else{
                System.out.println("未找到指定节点！");
            }
        }else{
            System.out.println("二叉树为空！");
        }
    }
    // 后序查找
    public void postOrderSearch(int no){
        if (root != null){
            HeroNode res = root.postOrderSearch(no);
            if (res != null){
                System.out.println(res);
            }else{
                System.out.println("未找到指定节点！");
            }
        }else{
            System.out.println("二叉树为空！");
        }
    }

    // 删除指定编号的节点
    public void deleteNode(int no){
        if (root != null){  // 判断根节点是否为空
            if (root.no == no){ // 判断根节点是否为目标节点
                root = null;
            }else{
                root.deleteNode(no);    // 从根节点开始递归遍历子节点
            }
        }else{
            System.out.println("二叉树为空");
        }
    }

}

/**
 * 模拟二叉树的节点
 */
class HeroNode{
    public int no;
    public String name;
    public HeroNode left;   // 左子节点
    public HeroNode right;  // 右子节点

    public HeroNode(int no, String name){
        this.no = no;
        this.name = name;
    }
    // 添加左子节点
    public void addLeftNode(HeroNode node){
        this.left = node;
    }
    // 添加右子节点
    public void addRightNode(HeroNode node){
        this.right = node;
    }
    // 前序遍历：根->左->右
    public void preOrder(){
        System.out.println(this);   // 打印本节点
        if (this.left != null){     // 递归打印左子节点
            this.left.preOrder();
        }
        if (this.right != null){    // 递归打印右子节点
            this.right.preOrder();
        }
    }
    // 中序遍历：左->根->右
    public void midOrder(){
        if (this.left != null){ // 递归打印左子节点
            this.left.midOrder();
        }
        System.out.println(this);   // 打印本节点
        if (this.right != null){
            this.right.midOrder();  // 递归打印右子节点
        }
    }
    // 后序遍历：左->右->根
    public void postOrder(){
        if (this.left != null){ // 递归打印左子节点
            this.left.postOrder();
        }
        if (this.right != null){    // 递归打印右子节点
            this.right.postOrder();
        }
        System.out.println(this);   // 打印本节点
    }

    // 前序查找
    public HeroNode preOrderSearch(int no){
        if (this.no == no){ // 先查根
            return this;
        }
        HeroNode res = null;
        if (this.left != null){ // 再查左
            res = this.left.preOrderSearch(no);
            if (res != null){
                return res;
            }
        }
        if (this.right != null){    // 最后查右
            res = this.right.preOrderSearch(no);
        }
        return res;
    }
    // 中序查找
    public HeroNode midOrderSearch(int no){
        HeroNode res = null;
        if (this.left != null){ // 先查左
            res = this.left.midOrderSearch(no);
        }
        if (res != null){
            return res;
        }
        if (this.no == no){ // 再查根
            return this;
        }
        if (this.right != null){    // 最后查右
            res = this.right.midOrderSearch(no);
        }
        return res;
    }
    // 后序查找
    public HeroNode postOrderSearch(int no){
        HeroNode res = null;
        if (this.left != null){
            res = this.left.postOrderSearch(no);
        }
        if (res != null){
            return res;
        }
        if (this.right != null){
            res = this.right.postOrderSearch(no);
        }
        if (res != null){
            return res;
        }
        if (this.no == no){
            return this;
        }
        return null;
    }

    // 删除节点：由于节点只记录下自己的左、右子节点的信息，因为只能通过待删除节点的父节点来删除自己
    public void deleteNode(int no){
        if (this.left != null && this.left.no == no){   // 判断左子节点是否是目标节点
            this.left = null;   // 删除节点，如果节点为父节点，则子树全部删除
            return;
        }
        if (this.right != null && this.right.no == no){ // 判断右子节点是否为目标节点
            this.right = null;  // 删除节点，若节点为父节点，则子树全部删除
            return;
        }
        if (this.left != null){ // 如果左子树不为空，左子树递归执行
            this.left.deleteNode(no);
        }
        if (this.right != null){    // 如果右子树不为空，右子树递归执行
            this.right.deleteNode(no);
        }
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}
